package demo12;

import demo11.Tree;

import java.util.ArrayList;
import java.util.List;

public class Tree2 {



    static class TreeNode{
            public char val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode (char val){
                this.val=val;
                this.left=null;
                this.right=null;
            }
        }
        //创建树
        public demo11.Tree.TreeNode creat()
        {
            demo11.Tree.TreeNode node1=new demo11.Tree.TreeNode('A');
            demo11.Tree.TreeNode node2=new demo11.Tree.TreeNode('B');
            demo11.Tree.TreeNode node3=new demo11.Tree.TreeNode('C');
            demo11.Tree.TreeNode node4=new demo11.Tree.TreeNode('D');
            demo11.Tree.TreeNode node5=new demo11.Tree.TreeNode('E');
            demo11.Tree.TreeNode node6=new demo11.Tree.TreeNode('F');
            demo11.Tree.TreeNode node7=new demo11.Tree.TreeNode('G');
            node1.left=node2;
            node1.right=node3;
            node2.left=node4;
            node2.right=node5;
            node3.left=node6;
            node3.right=node7;
            return node1;

        }
        //前序遍历
        public void prevnode(demo11.Tree.TreeNode head){
            if(head==null){
                return;
            }
            System.out.print(head.val+" ");
            prevnode(head.left);
            prevnode(head.right);
        }
        //中序遍历
        public void inorder(demo11.Tree.TreeNode head){
            if(head==null){
                return;
            }
            inorder(head.left);
            System.out.print(head.val+" ");
            inorder(head.right);
        }
        public  void pastorder(demo11.Tree.TreeNode head){
            if(head==null){
                return;
            }
            pastorder(head.left);
            pastorder(head.right);
            System.out.print(head.val+" ");
        }
        //第二种前序遍历
        List<Character> list=new ArrayList<>();
        public List<Character> pre(demo11.Tree.TreeNode head){
            if(head==null){
                return list;
            }
            list.add(head.val);
            pre(head.left);
            pre(head.right);
            return list;
        }
        //第三种前序遍历

        public List<Character> pre2(demo11.Tree.TreeNode head) {
            List<Character> list=new ArrayList<>();
            if(head==null){
                return list;
            }
            list.add(head.val);
            List<Character> list1=pre2(head.left);
            list.addAll(list1);
            List<Character> list3=pre2(head.right);
            list.addAll(list3);
            return list;
        }
        //二叉树获取结点个数第一种方法
        public static int size=0;
        public int size(demo11.Tree.TreeNode head){
            if(head==null){
                return 0;
            }
            size++;
            size(head.left);
            size(head.right);
            return size;
        }
        //二叉树获取结点个数第二种方法
        public int size1(demo11.Tree.TreeNode head){
            if(head==null){
                return 0;
            }
            return size1(head.left)+size1(head.right)+1;
        }
        //获取叶子结点个数
        public static int leafcount;
        public int getLeafNode(demo11.Tree.TreeNode head ){
            if(head==null){
                return 0;
            }
            if(head.left==null&&head.right==null){
                leafcount++;
            }
            getLeafNode(head.left);
            getLeafNode(head.right);
            return leafcount;
        }
        //获取第k层结点数=第k-1层左右子树的孩子节点个数
        public int getlevel(demo11.Tree.TreeNode head, int k){
            if(head==null){
                return 0;
            }
            if(k==1){
                return 1;
            }
            return (getlevel(head.left,k-1)+   //向前走一步
                    getlevel(head.right,k-1));
        }
        //求二叉树的高度=左树高度与右树高度的最大值+1
        public int getHeight(demo11.Tree.TreeNode head){
            if(head==null){
                return 0;
            }
            int leftHeight=getHeight(head.left);
            int rightHeight=getHeight(head.right);
            return Math.max(leftHeight,rightHeight)+1;
        }
        //检测value值是否存在，根节点不是的话找左边遇到null一层层找左子树的右边没有找右边
        public demo11.Tree.TreeNode findval(demo11.Tree.TreeNode head, char ch){
            if(head==null){
                return null;
            }
            if(head.val==ch){
                return head;
            }
            demo11.Tree.TreeNode left=findval(head.left,ch);
            if(left!=null){
                return left;
            }
            demo11.Tree.TreeNode right=findval(head.right,ch);
            if(right!=null){
                return right;
            }
            return null;
        }
        //判断两棵树的结构、节点值是否相同
        public boolean isSame(demo11.Tree.TreeNode p, demo11.Tree.TreeNode q){
            if(p!=null&&q==null||p==null&&q!=null){ //判结构
                return false;
            }
            if(p==null&&q==null){   //判结构
                return true;
            }
            if(q.val!= p.val){      //判节点值
                return false;
            }
            return isSame(p.left,q.left)&&isSame(p.right,q.right);
        }
        //两棵二叉树判断一棵二叉树中是否包括另一棵二叉树的某节点与这个节点的所有子树
        //方法是判断当前子树父节点是否与根节点一致或者与该子树与左子树相同或者该子树与右子树相同
        public boolean isSubtree(demo11.Tree.TreeNode head1, demo11.Tree.TreeNode head2){
            if(head1==null){
                return false;   //空树
            }
            if(isSame(head1,head2)){
                return true;
            }
            if(isSame(head1.left,head2)){       //判此树是否等于左子树
                return true;
            }
            if(isSame(head1.right,head2)){  //判此树是否等于右子树
                return true;
            }
            return false;
        }
        //翻转二叉树：每个节点左右相互交换
        public demo11.Tree.TreeNode inverTree(demo11.Tree.TreeNode head){
            if(head==null){
                return null;
            }
            if(head.left==null&&head.right==null){
                return head;
            }
            demo11.Tree.TreeNode tmp=head.left;
            head.left=head.right;
            head.right=tmp;
            inverTree(head.left);//左树
            inverTree(head.right);//右树
            return head;
        }
        //对称二叉树（给你一个二叉树的根节点判断它是否对称，判左子树左与右子树的右相同，左子树的右与右子树的左相同）
    public boolean isSymmetric(Tree.TreeNode head){
            if(head==null){
                return true;    //头结点同为空返回true
            }
            return isSymmetricchild(head.left,head.right);//判左子树和右子树

    }
    public boolean isSymmetricchild(Tree.TreeNode left,Tree.TreeNode right){
            //判结构
        if(left== null&&right==null){
            return true;
        }   //两边为空返回true不用再判值
        if(left==null&&right!=null||left!=null&&right==null){   //一个为空另一边不为null直接返回false，不用在判断值
            return false;
        }
        if(left.val!= right.val){   //判值，只要值不同一定为false不用再去判结构
            return false;
        }
        return isSymmetricchild(left.left,right.left)&&isSymmetricchild(left.right,right.left);
    }
        //判断平衡树
    public boolean balance(Tree.TreeNode head){
            if(head==null)
            {
                return true;
            }
            int leftHeight=height(head.left);
           int rightHeight=height(head.right);
            return Math.abs(leftHeight-rightHeight)<2&&balance(head.left)&&balance(head.right);
    }
    public int height(Tree.TreeNode head){
            if(head==null){
                return 0;
            }
            int left=height(head.left);
            int right=height(head.right);
            return left>right?left+1:right+1;
    }


    }
